package com.xieyong.leetcode;

public class Leetcode2411 {
    public static void main(String[] args) {

        Leetcode2411 leetcode2411 = new Leetcode2411();
        int[] nums = {1, 2, 3};
        int[] ints = leetcode2411.smallestSubarrays(nums);
        System.out.println(ints);
    }

    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length, presum = 0;
        int[] ret = new int[n];
        int[][] arr = new int[n+1][30];
        for(int i=1;i<n+1;i++){
            for(int j=0;j<30;j++){
                arr[i][j] = arr[i-1][j] + ((nums[i-1]>>j) & 1);
            }
        }
        int[] max = new int[n];
        int temp = 0;
        for(int i=n-1;i>=0;i--){
            temp|=nums[i];
            max[i] = temp;
        }
        for(int i=1;i<n+1;i++){
            int left = i, right = n;
            while(left<=right){
                int mid = left+(right-left)/2;
                if(check(max[i-1], arr[mid], arr[i-1])){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }
            ret[i-1] = left-i+1;
        }
        return ret;
    }
    public boolean check(int tar, int[] r, int[] l){
        int temp = 0;
        for(int i=0;i<30;i++){
            if(r[i]>l[i]) temp|=(1<<i);
        }
        return temp>=tar;
    }
}
